Array is a common, useful, and important data structure for computer systems to store and process data. An array is a set of consecutive memory locations grouped under one name, where each individual location is accessed by its index or subscript. It is typically used in computer science to implement static lookup tables to hold multiple values which have the same data type. Sorting an array is useful in organizing data in ordered form and recovering them rapidly.
Elements within a sorted array are found using a binary search, in O(log n); thus sorted arrays are suited for cases when one needs to be able to look up elements quickly. The complexity for lookups is the same as for self-balancing binary search trees.
Inserting and deleting elements in a sorted array, however, is known to be costly. The insertion and deletion of elements in a sorted array executes at O(n). This is due to the need to shift all the elements following the element to be inserted or deleted. In comparison, a self-balancing binary search tree inserts and deletes at O(log n).
For instance, when establishing a new sorted array with n elements, the cost is O(n2), for inserting all n elements, one-by-one, to the array. When n is large, the cost is prohibitively high and renders regular array useless for storing sorted data elements.
Arrays, however, are simple and have good quality in reference of locality. In modern computer systems, arrays may take advantage of the cache memory to have good performance.